/*
 *  heap.h
 *  kangmodb
 *
 *  Created by 강모 김 on 11. 4. 24..
 *  Copyright 2011 강모소프트. All rights reserved.
 *
 */

#ifndef _KD_HEAP_H_
#define _KD_HEAP_H_ (1)

#include <map>

template<class keyT, class dataT>
class kdHeap
{
private :
/*
	typedef typename std::multimap<keyT, dataT> keymap_t;
	typedef typename std::pair<keyT, dataT> pair_t;
*/
	typedef typename std::multimap<u64, void*> keymap_t;
	typedef typename std::pair<u64, void*> pair_t;

	keymap_t mmap_;
	
public :
	kdHeap() : mmap_() 
	{
	}
	~kdHeap() 
	{
	}
	bool empty() const
	{
		return mmap_.empty();
	}
	KD_VOID add(const keyT& key, const dataT& data)
	{
		KD_TRY
		{
			mmap_.insert( pair_t(key, data) );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	KD_VOID remove(const keyT& key, const dataT& data)
	{
		KD_TRY
		{
			keymap_t::iterator it;
			for (it = mmap_.find(key); it != mmap_.end(); it++ )
			{
				// find the element that has the same data
				if ( it->second == data ) {
					mmap_.erase( it );
					break;
				}
			}
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	KD_VOID getMin(keyT * key) const
	{
		KD_TRY
		{
			KD_ASSERT( key != NULL );
			KD_ASSERT( ! mmap_.empty() );
			keymap_t::const_iterator it = mmap_.begin();
			*key = (*it).first;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	KD_VOID getMax(keyT * key) const
	{
		KD_TRY
		{
			KD_ASSERT( key != NULL );
			KD_ASSERT( ! mmap_.empty() );
			keymap_t::const_reverse_iterator it = mmap_.rbegin();
			*key = (*it).first;
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
};

#endif /*_KD_HEAP_H_*/